import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/12 15:44
 * @description 并查集
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int minSwapsCouples(int[] row) {
        int len = row.length;
        int N = len / 2;
        UnionFind unionFind = new UnionFind(N);
        for (int i = 0; i < len;  i += 2) {
            // 如果同一对情侣坐在一起，【2.3】 【9，8】,那么取余之后肯定相等
            unionFind.union(row[i] / 2, row[i + 1] /2);
        }
        // 至少交换的次数 = 所有情侣的对数 - 并查集里连通分量的个数
        return N - unionFind.getCount();
    }
    private static class UnionFind{
        int[] parent;
        /**
         * 连同分量的个数
         */
        int count;

        public int getCount() {
            return count;
        }
        UnionFind(int n) {
            count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int x) {
            if (x != parent[x]) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            parent[rootX] = rootY;
            count--;
        }
    }
}

